import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

public class TestStack {
    public static String removeDuplicates(String s) {
        StringBuilder ret = new StringBuilder();
        char[] ch = s.toCharArray();

        for (int i = 1; i < ch.length; i++){
            if (ret.length() > 0 && ch[i] == ret.charAt(ret.length() - 1)){
                ret.deleteCharAt(ret.length() - 1);
            }else {
                ret.append(ch[i]);
            }
        }

        return ret.toString();
    }

    public static boolean backspaceCompare(String ss, String tt) {
        //处理一个字符串
        String s = handString(ss);
        String t = handString(tt);

        //判断两个字符串是否相同
        for (int i = 0; i < s.length(); i++){
            for (int j = 0; j < t.length(); j++){
                if (s.charAt(i) != t.charAt(j)){
                    return false;
                }
            }
        }

        return true;
    }

    public static String handString(String ss){
        StringBuilder ret = new StringBuilder();

        char[] s = ss.toCharArray();
        for (char ch : s){
            if (ret.length() > 0 && ch == '#'){
                ret.deleteCharAt(ret.length() - 1);
            }else {
                ret.append(ch);
            }
        }

        return ret.toString();
    }

    public static int calculate(String ss) {
        Deque<Integer> deque = new ArrayDeque();
        char op = '+';

        char[] s = ss.toCharArray();
        int i = 0;
        for (i = 0; i < s.length;){
            if (s[i] == ' '){
                i++;
            }else if (s[i] >= '0' && s[i] <= '9'){
                //提取多位数
                int tmp = 0;
                while (i < s.length && s[i] >= '0' && s[i] <= '9'){
                    tmp = tmp * 10 + s[i];
                    i++;
                }

                if (op == '+'){
                    deque.push(tmp);
                }else if (op == '-'){
                    deque.push(-tmp);
                }else if (op == '*'){
                    deque.push(deque.pop() * tmp);
                }else{
                    deque.push(deque.pop() / tmp);
                }
            }else{
                op = s[i];
                i++;
            }
        }

        int ret = 0;
        while (!deque.isEmpty()){
            ret += deque.pop();
        }

        return ret;
    }

    public static String decodeString(String ss) {
        Stack<StringBuffer> st = new Stack<>();
        Stack<Integer> in = new Stack<>();

        char[] s = ss.toCharArray();
        int i = 0, n = ss.length();

        while (i < n){
            if (s[i] >= '0' && s[i] <= '9'){
                //是数字，提取数字
                int tmp = 0;

                while (i < n && s[i] >= '0' && s[i] <= '9'){
                    tmp = tmp * 10 + (s[i] - '0');
                    i++;
                }
                in.push(tmp);
            }else if (s[i] == '['){
                i++;
                StringBuffer tmp = new StringBuffer();

                while(i < n && s[i] >= 'a' && s[i] <= 'z'){
                    tmp.append(s[i]);
                    i++;
                }
                st.push(tmp);
            }else if (s[i] == ']'){
                //解析
                int count = in.pop();
                StringBuffer tmp = st.pop();

                while (count-- > 0){
                    st.peek().append(tmp);
                }

                i++;
            }else {
                StringBuffer tmp = new StringBuffer();

                while(i < n && s[i] >= 'a' && s[i] <= 'z'){
                    tmp.append(s[i]);
                    i++;
                }
                st.peek().append(tmp);
            }
        }

        return st.peek().toString();
    }

    public static boolean validateStackSequences(int[] pushed, int[] popped) {
        StringBuffer st = new StringBuffer();
        int i = 0;

        for (int x : pushed){
            st.append(x);

            while (i < st.length() && (st.charAt(st.length() - 1) - '0') == popped[i]){
                st.deleteCharAt(st.length() - 1);
                i++;
            }
        }

        return i == (pushed.length);
    }


    public static String convert(String s, int numRows) {
        int len = s.length(), d = 2 * numRows - 2;
        StringBuffer st = new StringBuffer();

        for (int index = 0; index < len; index += d){
            st.append(s.charAt(index));
        }

        for (int i = 1; i < numRows - 1; i++){

            for (int index1 = i, index2 = d - index1; index1 < len || index2 < len; index1 += d, index2 += d){
                if (index1 < len){
                    st.append(s.charAt(index1));
                }

                if (index2 < len){
                    st.append(s.charAt(index2));
                }


            }
        }

        for (int index = numRows - 1; index < len; index += d){
            st.append(s.charAt(index));
        }

        return st.toString();
    }
    public static void main(String[] args) {
        //removeDuplicates("abbaca");
        //backspaceCompare("ab#c", "ad#c");
        //calculate("3+2*2");
        //decodeString("3[a]2[bc]");
        //validateStackSequences(new int[]{1,0}, new int[]{1,0});
        convert("A", 1);
    }


}
